Livré à domicile ! (d'après BAC ES, Liban 2019)

Énoncé

Un restaurateur décide de proposer des livraisons à domicile. Il fait un essai avec huit clients. Sur le graphe ci-dessous, les sommets représentent les différents lieux d'habitation de ces huit clients. Les arêtes représentent les rues et les valeurs indiquent les durées moyennes des trajets exprimées en minutes.

1. Répondre aux questions suivantes en justifiant.
    a. Existe-t-il un parcours qui emprunte toutes les rues une et une seule fois ?
    b. Un tel parcours peut-il partir de  \(H_1\)  et y revenir ?

2. En utilisant l'algorithme de Dijkstra, déterminer le temps minimal pour aller de  \(H_4\)  vers  \(H_8\) . Préciser le trajet correspondant.